package com.javabasic.algorithm.sword_of_offer;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/9 11:47 下午
 */
public class 剑指_Offer_04_二维数组中的查找 {

    int[][] subElement = new int[][]{{-1,0},{0,-1}};

    /**
     * 测试用例
     * [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
     * 5
     * [[-1,3]]
     * -1
     * [[]]
     * 1
     * [[1,3,5]]
     * 3
     *
     * 解法：BFS+备忘录 算法，同理也可以用 DFS+备忘录 解题
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row = matrix.length;
        if (row == 0) {
            return false;
        }
        int col = matrix[0].length;

        int[][] unVisit = new int[row][col];
        Queue<MatrixNode> queue = new LinkedList<>();
        MatrixNode matrixNode = new MatrixNode(row - 1, col - 1, matrix[row - 1][col - 1]);
        queue.offer(matrixNode);
        unVisit[row-1][col-1] = 1;
        MatrixNode currentValue;
        int tempx, tempy;
        while (!queue.isEmpty()) {
            currentValue = queue.poll();
            System.out.println(currentValue);
            if (currentValue.value == target) {
                return true;
            }
            for (int i = 0; i < 2; i++) {
                tempx = currentValue.row+subElement[i][0];
                tempy = currentValue.col+subElement[i][1];
                System.out.println(tempx + " " + tempy);
                if (tempx >= 0 && tempx < row && tempy >= 0 && tempy < col & unVisit[tempx][tempy] == 0) {
                    matrixNode = new MatrixNode(tempx, tempy, matrix[tempx][tempx]);
                    queue.offer(matrixNode);
                    unVisit[tempx][tempy] = 1;
                }
            }
        }

        return false;

    }

    class MatrixNode {
        int row;
        int col;
        int value;

        public MatrixNode(int row, int col, int value) {
            this.row = row;
            this.col = col;
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            MatrixNode that = (MatrixNode) o;
            return row == that.row && col == that.col && value == that.value;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col, value);
        }

        @Override
        public String toString() {
            return "MatrixNode{" +
                    "row=" + row +
                    ", col=" + col +
                    ", value=" + value +
                    '}';
        }

        public int getRow() {
            return row;
        }

        public void setRow(int row) {
            this.row = row;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int col) {
            this.col = col;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }
}
